import java.util.*;

/**
 * Created With IntelliJ IDEA
 * Description:leetcode:692. 前K个高频单词
 * <a href="https://leetcode.cn/problems/top-k-frequent-words/description/">...</a>
 * User: DELL
 * Data: 2023-03-04
 * Time: 18:07
 */
public class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        //统计每个单词出现的次数,放入hashMap中
        Map<String,Integer> hashMap = new HashMap<>();
        for (String word : words) {
            int num = hashMap.getOrDefault(word,0);
            hashMap.put(word,num+1);
        }
        //从hashMap中拿出每一对键值对
        ArrayList<Map.Entry<String,Integer>> list = new ArrayList<>(hashMap.entrySet());
        //建立小根堆,并传入比较器
        PriorityQueue<Map.Entry<String,Integer>> heap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue() != o2.getValue()) {
                    return o1.getValue() - o2.getValue();
                } else {
                    //这里由于要统计的是出现频率前K的单词,所以必须建立小根堆
                    //但最后要求按照出现次数和字典序输出单词,因此最后应该将堆中的单词取出,
                    //再逆转一下,即小根堆中的应该遵循逆字典序的顺序.
                    return o2.getKey().compareTo(o1.getKey());
                }
            }
        });
        //先将前k个放入heap中 (题目中规定K的取值是[0,不同单词的数目])
        for (int i = 0; i < k; i++) {
            heap.add(list.get(i));
        }
        //将剩余的和堆顶元素比较
        for (int i = k; i < list.size(); i++) {
            heap.add(list.get(i));
            heap.poll();
        }
        //将堆中元素按序取出
        List<String> res = new ArrayList<>(k);
        for (int i = 0; i < k; i++) {
            res.add(heap.poll().getKey());
        }
        //逆序
        Collections.reverse(res);
        return res;
    }
}